package basic.study.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @ClassName Mid15
 * @Description
 * @Company inspur
 * @Author Kevin
 * @Date 2020/6/17 9:23
 * @Version 1.0
 */
public class Mid15 {
    class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            Arrays.sort(nums);
            List<List<Integer>> list = new ArrayList<>();
            int k,l,r,sum;
            for (k = 0; k < nums.length - 2; k++) {
                if (k > 0 && nums[k-1] == nums[k]) {//跳过重复值
                    continue;
                }
                l = k + 1;
                r = nums.length - 1;
                sum = 0 - nums[k];
                while (l < r) {
                    if (nums[l] + nums[r] == sum) {
                        //去除重复值
                        list.add(Arrays.asList(nums[k], nums[l], nums[r]));
                        while (l < r && nums[l] == nums[l+1]) l++;
                        while (l < r && nums[r] == nums[r-1]) r--;
                        l++;
                        r--;
                    } else if(nums[l] + nums[r] < sum) {
                        l++;
                    } else {
                        r--;
                    }
                }
            }
            return list;
        }
    }
}
